#pragma once

#include "loirey_GLOBAL.h"
#include "loirey_MyMath.h"

namespace loirey
{

	template<typename TValue>
	class CAVLTreeNode
	{
	public:
		TValue Value;
		unsigned __int64 SubTreeSize;
		unsigned __int64 SubTreeHeight;
		CAVLTreeNode* Parent;
		CAVLTreeNode* LChild;
		CAVLTreeNode* RChild;

	public:
		static inline unsigned __int64 GetSubTreeHeight(CAVLTreeNode* pNode)
		{
			return (pNode==NULL ? 0 : pNode->SubTreeHeight);
		}
		static inline unsigned __int64 GetSubTreeSize(CAVLTreeNode* pNode)
		{
			return (pNode==NULL ? 0 : pNode->SubTreeSize);
		}
		static void SetRelation_Parent_And_LChild(CAVLTreeNode* pParent, CAVLTreeNode* pLChild)
		{
			if (pParent != NULL)
				pParent->LChild = pLChild;
			if (pLChild != NULL)
				pLChild->Parent = pParent;
		}
		static void SetRelation_Parent_And_RChild(CAVLTreeNode* pParent, CAVLTreeNode* pRChild)
		{
			if (pParent != NULL)
				pParent->RChild = pRChild;
			if (pRChild != NULL)
				pRChild->Parent = pParent;
		}
		static void SetRelation_Parent_And_NewChild(CAVLTreeNode* pParent, CAVLTreeNode* pOldChild, CAVLTreeNode* pNewChild)
		{
			if (pParent != NULL)
			{
				if (pParent->LChild == pOldChild)
					pParent->LChild = pNewChild;
				if (pParent->RChild == pOldChild)
					pParent->RChild = pNewChild;
			}
			if (pNewChild != NULL)
				pNewChild->Parent = pParent;
		}
	public:
		CAVLTreeNode()
		{
			SubTreeSize = SubTreeHeight = 1;
			Parent = LChild = RChild = NULL;
		}
		CAVLTreeNode(const TValue& Value)
		{
			this->Value = Value;
			SubTreeSize = SubTreeHeight = 1;
			Parent = LChild = RChild = NULL;
		}
		void DeleteChildren()
		{
			if (LChild != NULL)
				delete LChild;
			if (RChild != NULL)
				delete RChild;
			LChild = RChild = NULL;
			SubTreeSize = SubTreeHeight = 1;
		}
		~CAVLTreeNode()
		{
			DeleteChildren();
		}
		CAVLTreeNode<TValue>* Prev()
		{
			CAVLTreeNode<TValue>* pNode;
			CAVLTreeNode<TValue>* qNode;

			pNode = this;
			if (pNode->LChild == NULL)
				for ( qNode = NULL; (pNode!=NULL && pNode->LChild==qNode); )
				{
					qNode = pNode;
					pNode = pNode->Parent;
				}
			else
				for ( pNode = pNode->LChild; pNode->RChild != NULL; pNode = pNode->RChild )
					;
			return pNode;
		}
		CAVLTreeNode<TValue>* Next()
		{
			CAVLTreeNode<TValue>* pNode;
			CAVLTreeNode<TValue>* qNode;

			pNode = this;
			if (pNode->RChild == NULL)
				for ( qNode = NULL; (pNode!=NULL && pNode->RChild==qNode); )
				{
					qNode = pNode;
					pNode = pNode->Parent;
				}
			else
				for ( pNode = pNode->RChild; pNode->LChild != NULL; pNode = pNode->LChild )
					;
			return pNode;
		}
		void RefreshMyHeightAndSize()
		{
			unsigned __int64 tL,tR;
			tL = GetSubTreeHeight(LChild);
			tR = GetSubTreeHeight(RChild);
			SubTreeHeight = (tL>tR ? tL : tR) + 1;
			tL = GetSubTreeSize(LChild);
			tR = GetSubTreeSize(RChild);
			SubTreeSize = tL + tR + 1;
		}
		int MakeNodeSelfBalanced()
		{
			unsigned __int64 oldHeight, newHeight;
			unsigned __int64 LH,RH,LLH,LRH,RLH,RRH;
			CAVLTreeNode *pP;
			CAVLTreeNode *pL,   *pR;
			CAVLTreeNode *pLL,  *pLR;
			CAVLTreeNode *pRL,  *pRR;
			CAVLTreeNode *pLRL, *pLRR;
			CAVLTreeNode *pRLL, *pRLR;

			oldHeight = SubTreeHeight;
			RefreshMyHeightAndSize();
			newHeight = SubTreeHeight;

			pP = this->Parent;
			LH = GetSubTreeHeight(pL = LChild);
			RH = GetSubTreeHeight(pR = RChild);

			if (LH-RH == 2)
			{
				LLH = GetSubTreeHeight(pLL = LChild->LChild);
				LRH = GetSubTreeHeight(pLR = LChild->RChild);
				if (LLH>LRH)
				{
					SetRelation_Parent_And_NewChild(pP, this, pL);

					SetRelation_Parent_And_RChild(pL, this);

					SetRelation_Parent_And_LChild(this, pLR);

					this->RefreshMyHeightAndSize();

					pL->RefreshMyHeightAndSize();
					newHeight = pL->SubTreeHeight;
				}
				else
				{
					pLRL = pLR->LChild;
					pLRR = pLR->RChild;

					SetRelation_Parent_And_NewChild(pP, this, pLR);

					SetRelation_Parent_And_LChild(pLR, pL);
					SetRelation_Parent_And_RChild(pLR, this);

					SetRelation_Parent_And_RChild(pL, pLRL);
					SetRelation_Parent_And_LChild(this, pLRR);

					pL->RefreshMyHeightAndSize();
					this->RefreshMyHeightAndSize();

					pLR->RefreshMyHeightAndSize();
					newHeight = pLR->SubTreeHeight;
				}
			}
			else if (RH-LH == 2)
			{
				RRH = GetSubTreeHeight(pRR = RChild->RChild);
				RLH = GetSubTreeHeight(pRL = RChild->LChild);
				if (RRH>RLH)
				{
					SetRelation_Parent_And_NewChild(pP, this, pR);

					SetRelation_Parent_And_LChild(pR, this);

					SetRelation_Parent_And_RChild(this, pRL);

					this->RefreshMyHeightAndSize();

					pR->RefreshMyHeightAndSize();
					newHeight = pR->SubTreeHeight;
				}
				else
				{
					pRLL = pRL->LChild;
					pRLR = pRL->RChild;

					SetRelation_Parent_And_NewChild(pP, this, pRL);

					SetRelation_Parent_And_LChild(pRL, this);
					SetRelation_Parent_And_RChild(pRL, pR);

					SetRelation_Parent_And_RChild(this, pRLL);
					SetRelation_Parent_And_LChild(pR, pRLR);

					this->RefreshMyHeightAndSize();
					pR->RefreshMyHeightAndSize();

					pRL->RefreshMyHeightAndSize();
					newHeight = pRL->SubTreeHeight;
				}
			}
			return (int)(newHeight - oldHeight);
		}
	};

	template<typename TValue>
	class CAVLTree
	{
	public:
		typedef CAVLTreeNode<TValue> TypeOfNode;
	public:
		TypeOfNode *_Root;

	protected:
		void TraceUpBalancing(TypeOfNode* pNode)
		{
			int t;
			CAVLTreeNode<TValue>* qNode;

			while (pNode!=NULL && pNode!=_Root)
			{
				qNode = pNode->Parent;
				t = pNode->MakeNodeSelfBalanced();
				//if (t == 0) break;
				pNode = qNode;
			}
		}
	public:
		CAVLTree()
		{
			_Root = new TypeOfNode();
		}
		~CAVLTree()
		{
			delete _Root;
		}
		unsigned __int64 Size()
		{
			return TypeOfNode::GetSubTreeSize(_Root->LChild);
		}
		TypeOfNode* Begin()
		{
			TypeOfNode* pNode;
			for ( pNode = _Root; pNode->LChild != NULL; pNode = pNode->LChild )
				;
			return pNode;
		}
		const TypeOfNode* End()
		{
			return _Root;
		}
		void Clear()
		{
			_Root->DeleteChildren();
		}
		TypeOfNode* LowerBound(const TValue& Value)
		{
			TypeOfNode* pNode;
			TypeOfNode* qNode;
			qNode = _Root;
			pNode = qNode->LChild;
			for ( ; pNode != NULL; )
				if (!(pNode->Value < Value))
				{
					qNode = pNode;
					pNode = pNode->LChild;
				}
				else
					pNode = pNode->RChild;
			return qNode;
		}
		TypeOfNode* UpperBound(const TValue& Value)
		{
			TypeOfNode* pNode;
			TypeOfNode* qNode;
			qNode = _Root;
			pNode = pNode->LChild;
			for ( ; pNode != NULL; )
				if (Value < pNode->Value)
				{
					qNode = pNode;
					pNode = pNode->LChild;
				}
				else
					pNode = pNode->RChild;
			return qNode;
		}
		TypeOfNode* Find(const TValue& Value)
		{
			TypeOfNode* pNode = LowerBound(Value);
			for ( ; pNode != _Root; pNode = pNode->Next() )
			{
				if (Value == pNode->Value)
					return pNode;
				if (Value < pNode->Value)
					return _Root;
			}
			return _Root;
		}
		const TypeOfNode& GetValue(__int64 Index)
		{

			if (Index<0 || Index>=TypeOfNode::GetSubTreeSize(_Root->LChild))
				return _Root->Value;

			unsigned __int64 i = (unsigned __int64)Index;
			unsigned __int64 t;

			TypeOfNode* pNode = _Root->LChild;
			while (i >= 0)
			{
				t = TypeOfNode::GetSubTreeSize(pNode->LChild);
				if (i == t)
					break;
				else if (i < t)
					pNode = pNode->LChild;
				else
				{
					pNode = pNode->RChild;
					i -= t + 1;
				}
			}

			return pNode->Value;
		}
		TypeOfNode* Insert(const TValue& NewValue, bool fOverwrite = false)
		{
			TypeOfNode* pNode;
			TypeOfNode* pNewNode = new TypeOfNode(NewValue);

			pNode = _Root;
			for ( ; ; )

				if (pNode==_Root || !(pNode->Value < NewValue))
					if (pNode->LChild == NULL)
					{
						pNode->LChild = pNewNode;
						pNewNode->Parent = pNode;
						break;
					}
					else
						pNode = pNode->LChild;
				else if (pNode->Value < NewValue)
					if (pNode->RChild == NULL)
					{
						pNode->RChild = pNewNode;
						pNewNode->Parent = pNode;
						break;
					}
					else
						pNode = pNode->RChild;
				else
				{
					if (fOverwrite)
						pNode->Value = NewValue;
					delete pNewNode;
					pNewNode = pNode;
					break;
				}
			TraceUpBalancing(pNode);
			return pNewNode;
		}
		void Delete(TypeOfNode* pNode)
		{
			TypeOfNode *qNode, *rNode;
			unsigned __int64 Lt,Rt;

			if (pNode==NULL || pNode==_Root) return;
			for ( qNode = pNode; qNode != _Root; qNode = rNode )
			{
				if (qNode == NULL) return;
				rNode = qNode->Parent;
				if (rNode==NULL || rNode->LChild!=qNode && rNode->RChild!=qNode) return;
			}

			for ( ; (pNode->LChild!=NULL || pNode->RChild!=NULL); )
			{
				Lt = TypeOfNode::GetSubTreeHeight(pNode->LChild);
				Rt = TypeOfNode::GetSubTreeHeight(pNode->RChild);
				if (Lt == Rt)
				{
					Lt = TypeOfNode::GetSubTreeSize(pNode->LChild);
					Rt = TypeOfNode::GetSubTreeSize(pNode->RChild);
				}
				qNode = pNode;
				if (Lt >= Rt)
				{
					for ( pNode = pNode->LChild; pNode->RChild != NULL; pNode = pNode->RChild ) ;
					qNode->Value = pNode->Value;
				}
				else
				{
					for ( pNode = pNode->RChild; pNode->LChild != NULL; pNode = pNode->LChild ) ;
					qNode->Value = pNode->Value;
				}
			}

			qNode = pNode->Parent;
			TypeOfNode::SetRelation_Parent_And_NewChild(qNode, pNode, NULL);
			delete pNode;
			TraceUpBalancing(qNode);
		}
	};

}

